|
In theoretical computer science, a pattern language is a formal language that can be defined as the set of all particular instances of a string of constants and variables. Pattern Languages were introduced by Dana Angluin in the context of machine learning. == Definition == Given a finite set Σ of constant symbols and a countable set ''X'' of variable symbols disjoint from Σ, a pattern is a finite non-empty string of symbols from Σ∪''X''. The length of a pattern ''p'', denoted by |''p''|, is just the number of its symbols. The set of all patterns containing exactly ''n'' distinct variables (each of which may occur several times) is denoted by ''P''''n'', the set of all patterns at all by ''P'' *. A substitution is a mapping ''f'': ''P'' * → ''P'' * such that〔Angluin's notion of substitution differs from the usual notion of string substitution.〕 * ''f'' is a homomorphism with respect to string concatenation (⋅), formally: ∀''p'',''q''∈''P'' *. ''f''(''p''⋅''q'') = ''f''(''p'')⋅''f''(''q''); * ''f'' is non-erasing, formally: ∀''p''∈''P'' *. ''f''(''p'') ≠ ε, where ε denotes the empty string; and * ''f'' respects constants, formally: ∀''s''∈Σ. ''f''(''s'') = ''s''. If ''p'' = ''f''(''q'') for some patterns ''p'', ''q'' ∈ ''P'' * and some substitution ''f'', then ''p'' is said to be less general than ''q'', written ''p''≤''q''; in that case, necessarily |''p''| ≥ |''q''| holds. For a pattern ''p'', its language is defined as the set of all less general patterns that are built from constants only, formally: ''L''(''p'') = , where Σ+ denotes the set of all finite non-empty strings of symbols from Σ. For example, using the constants Σ = and the variables ''X'' = , the pattern 0''x''10''xx''1 ∈''P''1 and ''xxy'' ∈''P''2 has length 7 and 3, respectively. An instance of the former pattern is 00''z''100''z''0''z''1 and 01''z''101''z''1''z''1, it is obtained by the substitution that maps ''x'' to 0''z'' and to 1''z'', respectively, and each other symbol to itself. Both 00''z''100''z''0''z''1 and 01''z''101''z''1''z''1 are also instances of ''xxy''. In fact, ''L''(0''x''10''xx''1) is a subset of ''L''(''xxy''). The language of the pattern ''x''0 and ''x''1 is the set of all bit strings which denote an even and odd number, respectively. The language of ''xx'' is the set of all strings obtainable by concatenating a bit string with itself, e.g. 00, 11, 0101, 1010, 11101110 ∈ ''L''(''xx''). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Pattern language (formal languages)」の詳細全文を読む スポンサード リンク
|